package Leetcode;

public class problem_343 {
    public static int integerBreak(int n) {
        if(n<2){
            return 0;
        }
        if(n==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        int[] arr = new int[n+1];
        arr[2] = 1;
        arr[3] = 2;

        for(int i = 4;i<=n;i++){
            int maxq =Integer.MIN_VALUE;
            for(int j = 1;j<i-1;j++){
                maxq = Math.max(maxq,Math.max(arr[i-j]*j,(i-j)*j));
            }
            arr[i] = maxq;
        }
        return arr[n];
    }

    public static void main(String[] args) {
        System.out.println(integerBreak(6));
    }
}
